//2009/07/15 20:40:53
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

long long memo[2][51][50002];

class Polygons2
{
	public:
	long long number(vector <int> segments, int K)
	{
		long long count=0;
		sort(segments.begin(), segments.end());
		int p=0;
		//Case: k==1;
		//k is the number of segments needed, 
		//i means ith segments,
		//j means the length of the longest side;
		for(int i=0; i< segments.size(); i++)
		{
			for(int j=0; j<=50001;j++)
			{
				memo[p][i][j] = (i>0 ? memo[p][i-1][j]:0) + (segments[i]>=j ? 1:0);
			}
		}
		for(int k=2; k<K; k++)
		{
			p=1-p;
			memset(memo[p], 0, sizeof(memo[p]));
			for(int i=k-1;i<segments.size(); i++)
			{
				for(int j=0;j<=50001;j++)
				{
					memo[p][i][j] = memo[p][i-1][j]+memo[1-p][i-1][j-segments[i]>?0];
				}
			}
		}
		//Case: k==K;
		for(int i=1;i<segments.size();i++)
		{
			count+=memo[p][i-1][segments[i]+1];
		}
		return count;
	}
};
/*
 * It can be solved using Dynamic Programming.
 * Firstly, note that the only condition that needs to be taken care of is that the maximum side 
 * of the polygon should be lesser than the sum of the other sides. So, we sort the array, 
 * and iterate for the index of the element which will "be the maximum side". Let this index be X. 
 * Then all that we need to do is find the number of ways of choosing K - 1 numbers from the indices 0..X-1, 
 * such that they sum up to > Side[X].
 * 
 * Now, Define f(k,i,j) as the number of ways to choose exactly k segments out of the first i segments, 
 * such that the sum of the chosen numbers is >= j.
 * The basic recurrence is that either you choose the ith element or no, which gives : 
 * 
 * f(k,i,j) = f(k,i-1,j) + f(k-1,i-1,j-a[i])
 * 
 * A straightforward implementation would need O(K*size(segment[])*Maxside_50001) time and memory. 
 * To reduce the memory, only the last two rows can be stored(its a standard memory optimization in DP problems).
 * 
 * */
